package pro.softzhang.algo.lc400;

import pro.softzhang.algo.flag.difficulty.DRed;

import java.util.*;

@DRed
public class LC444_SequenceReconstruction {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int[][] seqs = {{1, 2}, {1, 3}};
        boolean f = new Solution().sequenceReconstruction(nums, seqs);
        System.out.println(f);
    }

    static class Solution {
        public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
            Map<Integer, Set<Integer>> graph = new HashMap<>();
            Map<Integer, Integer> inDegrees = new HashMap<>();
            for (int[] seq : sequences) {
                for (int num : seq) {
                    if(num < 1 || num > nums.length) {
                        return false;
                    }
                    graph.putIfAbsent(num, new HashSet<>());
                    inDegrees.putIfAbsent(num, 0);
                }

                for (int i = 0; i < nums.length - 1; i++) {
                    int num1 = nums[i], num2 = nums[i + 1];
                    if(!graph.get(num1).contains(num2)) {
                        graph.get(num1).add(num2);
                        inDegrees.put(num2, inDegrees.get(num2) + 1);
                    }
                }
            }

            Queue<Integer> q = new LinkedList<>();
            for (int num : inDegrees.keySet()) {
                if(inDegrees.get(num) == 0) {
                    q.add(num);
                }
            }

            List<Integer> built = new LinkedList<>();
            while (q.size() == 1) {
                int num = q.remove();
                built.add(num);
                for (int next : graph.get(num)) {
                    inDegrees.put(next, inDegrees.get(next) - 1);
                    if (inDegrees.get(next) == 0) {
                        q.add(next);
                    }
                }
            }

            int[] r = new int[built.size()];
            r = built.stream().mapToInt(i -> i).toArray();
            return Arrays.equals(r, nums);
        }
    }

    static class Solution1 {
        public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
            int n = nums.length;
            int[] indegrees = new int[n + 1];
            Set<Integer>[] graph = new Set[n + 1];
            for (int i = 1; i <= n; i++) {
                graph[i] = new HashSet<Integer>();
            }
            for (int[] sequence : sequences) {
                int size = sequence.length;
                for (int i = 1; i < size; i++) {
                    int prev = sequence[i - 1], next = sequence[i];
                    if (graph[prev].add(next)) {
                        indegrees[next]++;
                    }
                }
            }
            Queue<Integer> queue = new ArrayDeque<Integer>();
            for (int i = 1; i <= n; i++) {
                if (indegrees[i] == 0) {
                    queue.offer(i);
                }
            }
            while (!queue.isEmpty()) {
                if (queue.size() > 1) {
                    return false;
                }
                int num = queue.poll();
                Set<Integer> set = graph[num];
                for (int next : set) {
                    indegrees[next]--;
                    if (indegrees[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
            return true;
        }
    }
}
